﻿namespace Graph;

public class BFSSingleSourcePath
{
    private IGraph G;
    private bool[] visited;
    private Queue<int> queue = new Queue<int>();

    private int s;
    private float[] dis;
    private int[] pre;

    public BFSSingleSourcePath(IGraph G, int s)
    {
        this.G = G;
        this.s = s;
        visited = new bool[G.V];
        dis = new float[G.V];
        pre = new int[G.V];
        for (int i = 0; i < G.V; i++)
        {
            dis[i] = float.PositiveInfinity;
            pre[i] = -1;
        }

        BFS(s);
    }

    private void BFS(int s)
    {
        visited[s] = true;
        queue.Enqueue(s);
        dis[s] = 0;

        while (queue.Count != 0)
        {
            int v = queue.Dequeue();

            foreach (int w in G.Adj(v))
            {
                if (!visited[w])
                {
                    visited[w] = true;
                    dis[w] = dis[v] + 1;
                    pre[w] = v;
                    queue.Enqueue(w);
                }
            }
        }
    }
    public bool IsConnectedTo(int t)
    {
        return visited[t];
    }

    public float Dis(int t)
    {
        return dis[t];
    }

    public MyList<int> Path(int t)
    {
        MyList<int> res = new MyList<int>();
        if (!IsConnectedTo(t)) return res;

        int cur = t;
        while (cur != s)
        {
            res.Add(cur);
            cur = pre[cur];
        }
        res.Add(s);

        res.Reverse();
        return res;
    }

    //验证
    static void Main(string[] args)
    {
        IGraph graph = new AdjLinkList("图的深度优先遍历/g2.txt");
        int s = 0;

        DFSSingleSourcePath singleSourcePath = new(graph, s);
        for (int v = 0; v < graph.V; v++)
        {
            Console.WriteLine($"dfs:{s}->{v}: {singleSourcePath.Dis(v)} {singleSourcePath.Path(v)}");
        }

        Console.WriteLine();

        BFSSingleSourcePath singleSourcePath2 = new(graph, s);
        for (int v = 0; v < graph.V; v++)
        {
            Console.WriteLine($"bfs:{s}->{v}: {singleSourcePath2.Dis(v)} {singleSourcePath2.Path(v)}");
        }

        Console.Read();
    }
}
